//
// Created by liweimin on 2021/6/28.
//

//---------------���Ա�̬����˳��洢�ṹ-------------
#pragma once

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define LIST_INT_SIZE 100 //��ʼ������
#define LIST_INCREMENT 10 //����
#define ElementType int
typedef struct
{
    ElementType *elem; //���ݴ洢
    int length;        //���Ա���
    int list_size;     //���Ա��С
} SqlList;

/**
 * ����һ���յ����Ա�
 * @param sqlList
 * @return
 */
bool initSqlList(SqlList *sqlList)
{
    sqlList->elem = (ElementType *) malloc(LIST_INT_SIZE * sizeof(ElementType));
    if (!sqlList->elem)
    {
        printf("���Ա��ʼ��������ռ�ʧ��!");
        return false;
    }
    sqlList->length = 0;
    sqlList->list_size = LIST_INT_SIZE;
    return true;
}

/**
 * ����
 * @param sqlList
 */
void destroySqlList(SqlList *sqlList)
{
    free(sqlList->elem);
    sqlList->length = 0;
    sqlList->list_size = 0;
}
/**
 * �п�
 * @param sqlList
 * @return
 */
bool isEmpty(SqlList *sqlList)
{
    if (sqlList->length)
    {
        return false;
    }
    return true;

}
/**
 * ����
 * @param sqlList
 * @return
 */
bool isFull(SqlList *sqlList)
{
    return (sqlList->length == sqlList->list_size);
}

/**
 * ��ȡ����
 * @param sqlList
 * @return
 */
int getLength(SqlList *sqlList)
{
    return sqlList->length;
}

/**
 * ��ȡָ���±�Ԫ��
 * @param sqlList
 * @param i
 * @param elem
 * @return
 */
bool getElem(SqlList *sqlList, int i, ElementType *elem)
{
    if (i < 1 || i > sqlList->length)
    {
        return false;
    }
    *elem = sqlList->elem[i - 1];
    return true;

}

/**
 * ��ȡָ��Ԫ�صĵ�һ�γ���λ��
 * @param sqlList
 * @param elem
 * @param pos pos = -1��ʾ�����ڸ�Ԫ��
 * @return
 */
bool locateElem(SqlList *sqlList, ElementType elem, int *pos)
{
    *pos = -1;
    //��Ϊ�գ�����false
    if (isEmpty(sqlList))
    {
        return false;
    }
    for (int i = 0; i < sqlList->length; ++i)
    {
        if (sqlList->elem[i] == elem)
        {
            *pos = i + 1;
            return true;
        }
    }
    return false;
}

/**
 * ��ȡָ��Ԫ�ص�ǰһ��Ԫ��
 * @param sqlList
 * @param currentElem
 * @param priorElem
 * @return
 */
bool priorElem(SqlList *sqlList, ElementType currentElem, ElementType *priorElem)
{
    if (isEmpty(sqlList))
    {
        return false;
    }
    for (int i = 1; i < sqlList->length; ++i)
    {
        if (sqlList->elem[i] == currentElem)
        {
            *priorElem = sqlList->elem[i - 1];
            return true;
        }
    }
    return false;
}

/**
 * ��ȡָ��Ԫ�صĺ�һ��Ԫ��
 * @param sqlList
 * @param currentElem
 * @param nextElem
 * @return
 */
bool nextElem(SqlList *sqlList, ElementType currentElem, ElementType *nextElem)
{
    if (isEmpty(sqlList))
    {
        return false;
    }
    for (int i = 0; i < sqlList->length - 1; ++i)
    {
        if (sqlList->elem[i] == currentElem)
        {
            *nextElem = sqlList->elem[i + 1];
            return true;
        }
    }
    return false;
}
/**
 *����
 * @param sqlList
 * @return
 */
bool extend(SqlList *sqlList)
{
    ElementType *root = (ElementType *) realloc(sqlList->elem,
                                                (sqlList->list_size + LIST_INCREMENT) * sizeof(ElementType));
    if (!root)
    {
        return false;
    }
    sqlList->elem = root;
    sqlList->list_size += LIST_INCREMENT;
    return true;
}
/**
 *����
 * @param sqlList
 * @param pos
 * @param elem
 * @return
 */
bool insert(SqlList *sqlList, int pos, ElementType elem)
{
    if (pos < 1 || pos > sqlList->length > 1)
    {
        printf("����λ�÷Ƿ�!");
        return false;
    }

    //����--->����
    if (isFull(sqlList))
    {
        if (!extend(sqlList))
        {
            printf("���Ա�������Ŀǰ����Ϊ%d ������ʧ�ܣ�", sqlList->length);
        }
    }

    //�������
    for (int i = sqlList->length; i >= pos; --i)
    {
        sqlList->elem[i] = sqlList->elem[i - 1];
    }
    sqlList->elem[pos - 1] = elem;
    sqlList->length++;
    return true;

}

/**
 *ɾ��
 * @param sqlList
 * @param pos
 * @param elem
 * @return
 */
bool delete(SqlList *sqlList, int pos, ElementType *elem)
{
    if (isEmpty(sqlList))
    {
        printf("���Ա�Ϊ�գ�ɾ��Ԫ��ʧ�ܣ�");
        return false;
    }
    if (pos < 1 || pos > sqlList->length > 1)
    {
        printf("ɾ��λ�÷Ƿ�!");
        return false;
    }
    *elem = sqlList->elem[pos - 1];
    for (int i = pos - 1; i < sqlList->length - 1; ++i)
    {
        sqlList->elem[i] = sqlList->elem[i + 1];
    }
    sqlList->length--;
    return true;
}

/**
 *����
 * @param sqlList
 */
void traverse(SqlList *sqlList)
{
    for (int i = 0; i < sqlList->length; i++)
    {
        printf("%d\n", sqlList->elem[i]);
    }
}

/**
 *�ϲ�
 * @param sql1
 * @param sql2
 * @param sqlNew
 * @return
 */
bool merge(SqlList *sql1, SqlList *sql2, SqlList *sqlNew)
{
    sqlNew->elem = (ElementType *) malloc((sql1->length + sql2->length) * sizeof(ElementType));
    if (!sqlNew->elem)
    {
        printf("�ڴ�ռ����ʧ�ܣ�");
        return false;
    }
    sqlNew->list_size = sql1->length + sql2->length;
    sqlNew->length = 0;
    int pos = 1, j = 0, k = 0;
    while (j < sql1->length && k < sql2->length)
    {
        if (sql1->elem[j] <= sql2->elem[k])
        {
            if (!insert(sqlNew, pos++, sql1->elem[j]))
            {
                return false;
            }
            j++;
        } else
        {
            if (!insert(sqlNew, pos++, sql2->elem[k]))
            {
                return false;
            }
            k++;
        }
    }
    while (j < sql1->length)
    {
        if (!insert(sqlNew, pos++, sql1->elem[j]))
        {
            return false;
        }
        j++;
    }

    while (k < sql2->length)
    {
        if (!insert(sqlNew, pos++, sql2->elem[k]))
        {
            return false;
        }
        k++;
    }
}

bool merge1(SqlList *sql1, SqlList *sql2, SqlList *sqlNew)
{
    sqlNew->elem = (ElementType *) malloc((sql1->length + sql2->length) * sizeof(ElementType));
    if (!sqlNew->elem)
    {
        printf("内存分配失败！");
        return false;
    }
    sqlNew->list_size = sql1->length + sql2->length;
    sqlNew->length = 0;
    int pos = 1, j = 0, k = 0;
    while (j < sql1->length && k < sql2->length)
    {
        if (*(sql1->elem) <= *(sql2->elem))
        {
            *(sqlNew->elem++) = *(sql1->elem++);
        } else
        {
            *(sqlNew->elem++) = *(sql2->elem++);
        }
    }
    while (sql1->elem < (sql1->elem + sql1->length - 1))
    {
        *(sqlNew->elem++) = *(sql1->elem++);
    }
    while (sql2->elem < (sql2->elem + sql2->length - 1))
    {
        *(sqlNew->elem++) = *(sql2->elem++);
    }

}